package LimitedTimeGame.Day_0204;

/**
 * @author zxc
 * @date 2023/02/04 12:06
 **/

import org.springframework.jmx.export.naming.IdentityNamingStrategy;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 题目 ：构造出连续值的最大数
 * 题目详述 ：
 * 给你一个长度为 n的整数数组coins，它代表你拥有的n个硬币。
 * 第i个硬币的值为coins[i]。如果你从这些硬币中选出一部分硬币，它们的和为x，那么称，你可以构造出x。
 * 请返回从 0开始（包括0），你最多能构造出多少个连续整数。
 * 你可能有多个相同值的硬币。
 *
 *提示：
 * coins.length == n
 * 1 <= n <= 4 * 104
 * 1 <= coins[i] <= 4 * 104
 *
 */
public class GetMaximumConsecutive {
    /**
     * 思路 ：
     * 贪心法（思考性比较强）
     * ===>
     * （1）即，先假设所能够取得的结果;
     * （2）然后，检查该结果是否满足条件 || 检查该结果进一步处理后是否还能够满足题目条件;
     * （3）进行最后的处理;
     *
     * ===》
     * （1）基本思想 ：
     *  即，当coins数组中元素能够组成连续整数[0,x],若是加入新元素y,===> 即，扩展区间为[y,x+y];
     *  ===> 满足y <= x+1条件的话，即coins数组中元素能够组成连续整数为[0,x+y];
     * （2）对于coins数组进行排序（从小到大进行排序;）
     * （3）遍历coins数组中所有元素;
     *  即，当不选择任何coins数组中元素时，初始化所能够组成连续整数区间[0,0];
     * （4）选择添加后续coin元素时，
     *  未添加此coin元素时，所能够组成连续整数区间为[0,x];
     *  添加此coin元素后 && coin <= x + 1，即所能够组成连续整数区间为[0, x + coin];
     *
     * @param coins
     * @return
     */
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int result = 1;
        for (int coin : coins) {
            if(coin > result){
                break;
            }
            result += coin;
        }
        return result;
    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：O（nlogn）;
     * （2）空间复杂度 ：O(logn);（对于coins数组进行排序，所需要的logn栈空间;）
     */
}
